The demand for wireless data services, such as text messaging (SMS), multi-media messaging (MMS), mobile video and IPTV, demanding higher bandwidth is growing quickly. The third generation partnership project (3GPP) is developing the third generation mobile systems based on evolved GSM core networks and the radio access technology UMTS terrestrial radio access (UTRA) and has come up with a new orthogonal frequency division multiple access (OFDMA) based technology through the long term evolution (LTE) work, which provides a very efficient wireless solution. The OFDMA based air interface is often referred to as the evolved UMTS terrestrial radio access network (E-UTRAN).
The architecture of the LTE system is shown in FIG. 1. In LTE the downlink (DL) is based on orthogonal frequency division multiplexing (OFDM), while the uplink (UL) is based on a single carrier modulation method known as discrete Fourier transform spread OFDM (DFT-S-OFDM).
During initial access, a mobile station (MS) seeks access to the network in order to register and commence services. The random access (RA) serves as an uplink control procedure to enable the MS to access a communication network operated from a base station (BS) serving a communication cell. Since an initial access attempt cannot be scheduled by the network, the RA procedure is by definition contention based. Collisions may occur and an appropriate contention-resolution scheme needs to be implemented.
Including user data on the contention-based uplink is typically not spectrally efficient due to a need for guard periods and retransmissions. Therefore, for LTE it has been decided to separate a transmission of a random access burst (a preamble), the purpose of which is to obtain uplink synchronization, from a transmission of user data.
The LTE RA procedure serves two main purposes:                It lets the MS align its UL timing to that expected by the eNode B (see FIG. 1) in order to minimize interfering with other MSs transmissions. UL time alignment is a requirement in E-UTRAN before data transmissions may commence.        It provides means for the MS to notify the network of its presence and enables the eNode B to give the MS initial access to the system.        
In addition to the usage during initial access, the RA will also be used when the MS has lost the uplink synchronization or when the MS is in an idle or a low-power mode.
The basic RA procedure is a four-phase procedure, as outlined in FIG. 2, and is as follows:                In phase 1, the MS 18 transmits a random access preamble (step 21), allowing the eNode B (BS) to estimate the timing of the MS. Uplink synchronization is necessary as the MS otherwise cannot transmit any uplink data;        In phase 2, the network transmitting a timing advance command (step 22) to correct the uplink timing, based on the timing of preamble arrival in the first step. In addition to establishing uplink synchronization, phase 2 also assigns uplink resources and temporary identifier to the MS to be used in phase 3 of a random access procedure;        Phase 3, consists of signalling from the MS 18 to the network (step 23) using the UL-SCH similar to normal scheduled data. A primary function of this message is to uniquely identify the MS 18. The exact content of this signalling depends on the state of the MS 18, e.g., whether it is previously known to the network or not;        The final phase (phase 4), is responsible for contention resolution in case multiple MSs tried to access the system on the same resource.        
For cases where the network knows, in advance, that a particular MS will perform a Random Access Procedure to acquire uplink synchronization, a contention-free variety of the Random Access Procedure has been agreed. This effectively makes it possible to skip the Contention Resolution process of Phases 3 and 4 for important cases such as arrival to target cell at handover (HO) and arrival of DL data.
Phase 1—Random Access Preamble
Prior to sending a preamble, the MS shall synchronize to the downlink transmissions and read the Broadcast Control Channel (BCCH). The BCCH will reveal where the RA time slots are located, which frequency bands may be used, the settings of the power control parameters, and which preambles (sequences) are available.
At the next RA slot, the MS will send the preamble. The preamble sequence implicitly includes a random ID, which identifies the MS. LTE provides for each cell 64 such random IDs and thus 64 preambles.
If multiple RA frequency bands have been defined, the MS randomly selects one of them. The group of sequences allocated to a cell is partitioned into two subgroups. By selecting a preamble sequence from a specific subgroup, the MS can give a single-bit indication of its resource requirement and/or link quality. The particular sequence used for the preamble is randomly selected within the desired subgroup. This sequence implicitly contains a random ID, which serves as an MS identifier.
The eNode B estimates the UL timing of the MS based on the timing of the received preamble.
Phase 2—Random Access Response
After the preamble transmission, the MS waits for an RA Response message on the DL-SCH, the DL assignment which is indicated on the L1/L2 control channel (DPCCH). The RA Response message is transmitted semi-synchronously (i.e. within a window) to the reception of the RA Preamble in order to allow the scheduler more flexibility. The RA Response contains:                the same random MS identity as present in the preamble;        a time alignment message to provide the proper uplink timing to the MS;        a temporary Radio Network Temporary Identifier (RNTI) which is unique for the particular RA resource (time, channel and preamble) used in Phase 1. For initial access, the temporary RNTI shall be used for Phases 3 and 4;        a UL resource grant for transmission on UL-SCH in Phase 3.        
If no RA Response message has been received after a certain time following the preamble transmission, the MS shall send a new preamble at the next RA time slot. It shall select new, random parameters for the preamble sequence and the non-synchronized RA frequency band. Furthermore, the MS will increase the power level of the preamble to obtain a power ramping procedure similar as used in WCDMA.
Phase 3—First Scheduled UL Transmission
In Phase 3, the MS provides the network with a unique identifier in the message it transmits on UL-SCH according to the grant contained in the RA Response. The type of MS identifier, e.g. C-RNTI, TMSI, IMSI or IMEI, depends on to which extent the MS is already known in the network.
In case of initial access, the message is an RRC Connection Request message. In case of non-initial access, i.e. when the MS is already RRC_CONNECTED, the MS identifier is the C-RNTI and is signalled by a MAC layer. The transmission uses HARQ.
Phase 4—Contention Resolution
The purpose of the fourth phase is to resolve contention. Note that, from the second step, multiple MSs performing simultaneously random access attempts using the same preamble listen to the same response message and therefore have the same temporary identifier. Hence, in the fourth phase, the eNode B echoes the MS identity provided by the MS in Phase 3. Only a terminal which finds a match between the identity received in the fourth step and the identity transmitted as part of the third step will declare the random access procedure successful. This terminal will also transmit a hybrid ARQ acknowledge in the uplink. For non-initial access, i.e. when the MS is already RRC_CONNECTED, the MS identity is reflected on the L1/L2 control channel. If the MS has not yet been assigned a C-RNTI, the temporary identity from the second step is promoted to the C-RNTI, otherwise the MS keeps its already assigned C-RNTI.
Terminals which do not find a match between the identity received in Phase 4 and the respective identity transmitted as part of Phase 3 are considered to have failed the random access procedure and need to restart the random access procedure with Phase 1; selecting new random parameters for the preamble sequence and the RA frequency band. No hybrid ARQ feedback is transmitted from these terminals.
Contention-Free Random Access Procedure
For cases where the network knows, in advance, that a particular MS will perform a Random Access Procedure to acquire uplink synchronization, a dedicated preamble is reserved and assigned to the MS under consideration. Dedicated Preamble assignment for HO is handled by RRC, whereas preamble assignment for DL data arrival is handled by MAC. When the MS transmits the dedicated preamble in Phase 1, the network knows to which MS this preamble was assigned and can already at the time of detection of this preamble determine the identity of the MS. Thus no contention resolution is needed and the delay before data transmission can be resumed is reduced.
Random Access Back-Off Procedure
For the event of Random Access overload, a Random Access Back-Off procedure is supported. This procedure prevents immediate new Random Access attempts which would only worsen a collision situation.
Random Access Channel Physical Resource
A single RA opportunity consists of a time slot and a fixed bandwidth. The RA time slot length TRA shall accommodate the preamble sent by the MS and the required guard period (GP) to take into account the unknown uplink timing. FIG. 3 shows the access burst timing for two MSs 18a and 18b, where the preamble is denoted 31 and the guard period (GP) is denoted 32. The timing misalignment amounts to 6.7 μs/km. 3GPP has decided for a minimum TRA of 1 ms. Here the preamble length is then 800 μs plus a cyclic prefix of around 102.5 μs. A guard time of 97.5 μs suffices for cell radii up to 15 km. Larger guard periods and cyclic prefix are needed to accommodate timing uncertainties from cells larger than 15 km. Such large cells may also require longer preambles to increase the received energy. In order to support RA under various cell conditions RAN1 has defined additionally 3 RA preamble formats which require a TRA of 2 ms or even 3 ms. These larger slots are created by the eNode B by not scheduling traffic in the consecutive sub-frame(s). Those extended preambles contain repetitions of the 800 μs long part and/or a longer cyclic prefix.
For TDD an additional “short” RA is defined. The short RA preamble only spans 133 μs. Because of this very short duration the preamble will most likely not contain a cyclic prefix but a technique called overlap-and-add will be used to enable frequency-domain processing. At present many details regarding applicability and performance of this short RA are still open.
According to 3GPP, the bandwidth of a RA opportunity is 1.08 MHz (6 RB). The effective bandwidth utilized by the RA preamble is 1.05 MHz leaving small spectral guard bands on each side. This is necessary since RA and regular uplink data are separated in frequency-domain but are not completely orthogonal.
For FDD systems, RA opportunities do not occur simultaneously in different frequency bands but are separated in time. This spreads processing load out in the RA receiver. 3GPP defines RA configurations determining how often RA opportunities occur. In total 16 such configurations are defined, ranging from one RA opportunity every 20 ms (very low RA load) to one every 1 ms (very high RA load).
In TDD not all sub-frames are DL sub-frames reducing sub-frames that can be allocated to RA. To provide also in TDD configurations for high RA loads multiple RA opportunities can be scheduled in a single sub-frame.
In order to compensate for the rather low frequency diversity obtained within 1.05 MHz the RA opportunity hops in frequency-domain. For FDD RA opportunities are restricted to the outermost 6 RBs of the physical uplink shared channel at each band edge.
The TDMA/FDMA structure of the RA opportunities in FDD is visualized in FIG. 4 where the time and frequency configuration of the PRACH, PUSCH, and PUCCH in the LTE uplink is shown. In this example, three RA opportunities with 1 ms length exist in each frame. Here only one 1.08 MHz band is allocated to RA at each time whereas several bands are possible in case of TDD. The RA opportunities always occur at the band edges of the physical uplink shared channel directly adjacent to the physical uplink control channel.
Preamble Format
FIGS. 5a to 5d shows random access preambles, wherein FIG. 5a shows the detailed timing of the basic random-access preamble 31. The preamble 31 is prefixed with a cyclic prefix (CP) 51 to enable simple frequency domain processing. Its length is in the order of TGP+TDS=97.5+5 μs=102.5 μs, where TDS corresponds to the maximum delay spread and TGP corresponds to the maximum round trip time. The CP 51 insures that the received signal is always circular (after removing the CP in the RA receiver) and thus can be processed by FFTs. Therefore, the “active” random-access preamble duration is 1000 μs−2·TGP−TDS=800 μs. The RA subcarrier spacing is 1/800 μs=1250 Hz.
FIG. 5b to FIG. 5d show the extended preamble formats. The format of FIG. 5b has an extended CP 51 and is suited for cell radii up to approximately 100 km. However, since no repetition occurs this format is only suited for environments with good propagation conditions. The format of FIG. 5c contains a repeated main preamble 31 and a cyclic prefix 51 of approximately 200 μs. With an RA opportunity length of 2 ms the remaining guard period is also approximately 200 μs. This format supports cell radii of up to approximately 30 km. The format of FIG. 5d also contains a repeated main preamble 31 and an extended CP 51. Using an RA opportunity length of 3 ms this format supports cell radii of up to approximately 100 km. In opposite to format of FIG. 5b the format of FIG. 5d contains a repeated preamble 31 and is therefore better suited for environments with bad propagation conditions.
Zadoff-Chu Sequences
The requirements on the sequence comprising the preamble are two-fold: good auto-correlation function (ACF) properties and good cross-correlation function (CCF) properties. A sequence that has ideal (periodic) ACF and CCF properties is the Zadoff-Chu sequence. The periodic ACF of Zadoff-Chu sequence is only non-zero at time-lag zero (and periodic extensions) and the magnitude of the CCF is equal to the square-root of the sequence length N. Due to special properties of Zadoff-Chu sequences the number of sequences is maximized if N is chosen prime. This together with the requirement that the effective RA bandwidth N·1250 Hz should fit into 1.05 MHz leads to N=839.
A Zadoff-Chu sequence of length N can be expressed, in the frequency domain, as
                                          X            ZC                          (              u              )                                ⁡                      (            k            )                          =                  ⅇ                                    -              j                        ⁢                                                  ⁢            π            ⁢                                                  ⁢                          u                                                k                  ·                                      (                                          k                      +                      1                                        )                                                  N                                                                        (        1        )            where u is the index of the Zadoff-Chu sequence within the set of Zadoff-Chu sequences of length N. Out of one Zadoff-Chu sequence—in the following also denoted root sequence—multiple preamble sequences can be derived by cyclic shifting. Due to the ideal ACF of Zadoff-Chu sequence multiple mutually orthogonal sequences can be derived from a single root sequence by cyclic shifting one root sequence multiple times the maximum allowed round trip time plus delay spread in time-domain. The correlation of such a cyclic shifted sequence and the underlying root sequence has its peak no longer at zero but at the cyclic shift. If the received signal has now a valid round trip delay—i.e. not larger than the maximum assumed round trip time—the correlation peak occurs at the cyclic shift plus the round trip delay which is still in the correct correlation zone. FIG. 6a shows the correlation peak when the MS is close to Node B and FIG. 6b shows the correlation peak when the MS is almost at the cell border. In FIGS. 6a and 6b, 65 is the time delay which indicates the round trip delay and the arrows indicates the zones 0-5 indicating transmitted sequences. For small cells up to 1.5 km radii all 64 preambles can be derived from a single root sequence and are therefore orthogonal to each other. In larger cells not all preambles can be derived from a single root sequence and multiple root sequences must be allocated to a cell. Preambles derived from different root sequences are not orthogonal to each other.
One disadvantage of Zadoff-Chu sequences is their behaviour at high frequency offsets. A frequency-offset creates an additional correlation peak in time-domain. A frequency offset has to be considered high if it becomes substantial relative to the RA sub-carrier spacing of 1250 Hz, e.g. from 400 Hz upwards. The offset of the second correlation peak relative to the main peak depends on the root sequence. An offset smaller than TCS may lead to wrong timing estimates, whereas values larger than TCS increase the false alarm rate. In order to cope with this problem LTE has a high-speed mode (or better high frequency offset mode) which disables certain cyclic shift values and root sequences so that transmitted preamble and round trip time can uniquely be identified. Additionally a special receiver combining both correlation peaks is required. For cells larger than approximately 35 km no set of 64 preambles exists that allows unique identification of transmitted preamble and estimation of propagation delay, i.e. cells larger than 35 km cannot be supported in high speed mode.
Preamble Detection
A receiver at the eNodeB correlates the received signal with all the root sequences (Zadoff-Chu sequences) allocated to the eNodeB, see FIG. 7 If the correlation (height of the correlation peak) due to a preamble is higher than the detection threshold, then the preamble is detected. However, if the correlation is lower than the detection threshold then the preamble is not detected. We say in the latter case that we have a detection miss. The detection miss probability is the probability that the correlation between the root sequence and the received signal is less than the detection threshold when in fact a preamble was sent (i.e., we have a miss detection).
Correlation peaks may also occur due to noise or cross-interference from preambles derived from a different root sequence. A correlation due to noise or interference may become higher than the detection threshold, especially, if the detection threshold is set too low. In this case, no preamble is sent, however, the eNodeB concludes a preamble detection since the peak is above the threshold. We say that we have a false detection. The probability that a correlation peak due to noise or interference is higher than the detection threshold, i.e. we have a false detection, is called the false detection probability.
The correlation may be interpreted as the received power of a transmitted preamble. Hence, the detection performance is related to the preamble Signal power to Interference and Noise power Ratio, SINR. The notation of correlation and received power can be used interchangeably, and the cause of a missed detection can therefore be said to be due to insufficient correlation, or to insufficient received power.
From a user perspective, it is irrelevant if the random access attempt failed due to a miss detection or contention. Instead, it is the access probability that matters, which is the probability that a sent preamble is correctly detected without contention.
RACH Power Control
Power control has been agreed for RACH in LTE:PRACH(N)=min{PMAX, PO—RACH+PL+(N−1)ΔRACH+ΔPreamble}.                where        PRACH is the preamble transmit power,        N=1, 2, 3, . . . is the RACH attempt number,        PMAX is the maximum MS power,        P0—RACH is a 4-bit cell specific target received power signaled via BCCH with a granularity of 2 dB (difference in maximum and minimum P0—RACH is 30 dB),        PL is the path loss estimated by the MS,        ΔRACH is the power ramping step signaled via BCCH and represented by 2 bits (4 levels) with a granularity of 2 dB,        ΔPreamble is a preamble-based offset (format 0-3), see the Preamble format paragraph above.        
Note that RACH attempts N=2, 3, 4, . . . includes retransmissions where:                no RA Response message has been received by the MS (see FIG. 2),        the RA Response message is intended for another preamble (MS),        the contention resolution has failed and the MS has to try random access again.        
In essence, the MS will increase its transmission power until network access is granted. There is typically an upper bound on the number of retransmissions and, thus, number of power increases.
Drawbacks of Existing Solutions
One of the fundamental problems related to RACH optimization is to adjust a set of RA parameters, e.g., desired target receive power P0—RACH, such that random access performance requirements are satisfied, and excessive interference generated by RACH is avoided.
The setting of RA parameters depends on a multitude of factors including, chosen root sequence (in general the preambles allocated to a cell), whether the cell is in high-speed mode or not, interference from neighboring cells, cell size etc.
Typically a wide range of RA parameters are simulated and those settings that satisfy given requirements and that minimize the interference are chosen. This approach is, however, not satisfactory due to the several reasons, e.g.:                There is a need to perform extensive simulation test and field trials, which is very costly.        Simulations may not be accurate, hence, the derived set of parameters may be sub-optimal.        RA parameters need to be reconfigured if network characteristics changes, e.g., the inference levels increases, or preambles need to be changed, MSs start moving in a higher speed in a cell (due to for example a high way built).        Finding good set of parameter using simulation or field trials is a slow process and not sufficiently responsive to changes in network, hence, it may take a while before RACH is optimized.        One object of the present invention aims at alleviating the problems with today's solutions.        
Patent documents related to this invention, such as U.S. Pat. Nos. 7,072,327 and 6,487,420, describe automated tuning of RA, however, none of them addresses E-UTRAN and Zadoff-Chu based random access, which is used in E-UTRAN.